A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic unordered search of van Dam et al. (How powerful is adiabatic quantum computation? Proc. IEEE FOCS, pp. 279-287, 2001) and Roland and Cerf (Physical Review A 65, 042308, 2002) when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in $\log N$, where $N$ is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.
展开▼
机译：设计更快的量子绝热算法的常见技巧是在每个瞬间局部应用绝热条件。但是，通常很难确定最低的两个特征值之间的瞬时间隔，这是绝热条件下的基本要素。在本文中，我们提出了一种简单的线性代数技术，即使在这种情况下也能获得瞬时间隙的下限。作为说明，我们研究了Van Dam等人的绝热无序搜索。 （绝热量子计算的功能有多强大？IEEE FOCS，第279-287页，2001年）和Roland和Cerf（Physical Review A 65，042308，2002），当对角最终哈密顿量的非零项被a扰动时多项式（以$ \ log N $，其中$ N $是无序列表的长度）的数量。我们使用我们的技术，以最低的两个特征值之间的最小差距得出局部绝热程序运行时间的界限。
展开▼
